package 并查集;

public class UnionFind1 {
	private int[] parents;
	private int[] ranks;
	
	public UnionFind1(int capacity) {
		if (capacity <= 0) throw new IllegalArgumentException("Capacity must > 0");
		parents = new int[capacity];
		for (int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}
		ranks = new int[capacity];
		for (int i = 0; i < ranks.length; i++) {
			ranks[i] = 1;
		}
	}
	
	public int find(int v) {
		rangeCheck(v);
		while (v != parents[v]) {
			parents[v] = parents[parents[v]];
			v = parents[v];
		}
		return v;
	}
	
	public boolean isSame(int v1, int v2) {
		
		return find(v1) == find(v2);
	}
	
	public void union(int v1, int v2) {
		int p1 = find(v1);
		int p2 = find(v2);
		if (p1 == p2) return;
		
		if (ranks[p1] < ranks[p2]) {
			parents[p1] = p2;
		} else if (ranks[p1] > ranks[p2]) {
			parents[p2] = p1;
		} else {
			parents[p1] = p2;
			ranks[p2]++;
		}
	}
	
	private void rangeCheck(int v) {
		if (v < 0 || v >= parents.length) throw new IndexOutOfBoundsException();
	}
}
